package com.atguigu.distributed.lock.leecode.tree;

import com.atguigu.distributed.lock.leecode.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 *力扣中等437：路径总和3
 */
public class PathPlus3 {
    public int pathSum(TreeNode root,int targetSum){
        Map<Long,Integer> prefix = new HashMap<>();
        prefix.put(0L,1);
        return dfs(root,prefix,0,targetSum);
    }
    public int dfs(TreeNode root,Map<Long,Integer> prefix,long curr,int targetSum){
        if(root==null){
            return 0;
        }
        int ret = 0;
        curr+=root.data;
        ret = prefix.getOrDefault(curr-targetSum,0);
        prefix.put(curr,prefix.getOrDefault(curr,0)+1);
        ret+=dfs(root.left,prefix,curr,targetSum);
        ret+=dfs(root.right,prefix,curr,targetSum);
        prefix.put(curr,prefix.getOrDefault(curr,0)-1);
        return ret;
    }
}
class Solution2 {
    public int pathSum(TreeNode root, int targetSum) {
        Map<Long, Integer> prefix = new HashMap<Long, Integer>();
        prefix.put(0L, 1);
        return dfs(root, prefix, 0, targetSum);
    }

    public int dfs(TreeNode root, Map<Long, Integer> prefix, long curr, int targetSum) {
        if (root == null) {
            return 0;
        }

        int ret = 0;
        curr += root.data;

        ret = prefix.getOrDefault(curr - targetSum, 0);
        prefix.put(curr, prefix.getOrDefault(curr, 0) + 1);
        ret += dfs(root.left, prefix, curr, targetSum);
        ret += dfs(root.right, prefix, curr, targetSum);
        prefix.put(curr, prefix.getOrDefault(curr, 0) - 1);

        return ret;
    }
}

